package aco;

import java.util.ArrayList;
import java.util.Collections;

import aco.Ants.Ant;

import java.lang.management.*;

/**
 * contains the main entry point for the implementation of ACO
 * for solving the VRPTW problem on instances belonging to Solomon benchmark
 * 这是蚁群优化类，这个类中包含了蚁群优化的完整方法
 */
public class VRPTW_ACS implements Runnable {
    private volatile boolean isRunning = true;

    // indicates whether local search is used in the ACO algorithm
    public static boolean ls_flag = true;

    // indicates whether the thread was restarted from outside
    private boolean threadRestarted;

    private VRPTW vrpInstance;

    public VRPTW_ACS() {
    }

    public VRPTW_ACS(boolean threadStopped, VRPTW vrpInstance_) {
        this.threadRestarted = threadStopped;
        this.vrpInstance = vrpInstance_;
    }

    // do the work of running the ant colony which tries to solve the DVRPTW instance
    // using the available(known so far) customer requests
    public void run() {
        int counter = 0;
        isRunning = true;

        //System.out.println("Starting ant colony thread; isRunning=" + isRunning);
        while (isRunning) {

            // 1.如果ACS线程不是首次开启，则需要根据上次运行的最优解，更新信息素
            // the thread was restarted (i.e. it was previously stopped and started again)
            if (threadRestarted) {
                // compute the new value for the initial pheromone trail based on the current best solution so far
                int noAvailableNodes = vrpInstance.getIdAvailableRequests().size();
                Ants.trail_0 = 1. / ((double) (noAvailableNodes + 1) * (double) Ants.best_so_far_ant.total_tour_length);

                // preserve a certain amount of the pheromones from the previous run of the ant colony
                Ants.preservePheromones(vrpInstance);
            }

            // 2.构造蚁群 do the optimization task (work)
            construct_solutions(vrpInstance);
            //increase evaluations counter
            InOut.noEvaluations++; // 进行优化的次数？？？
            counter++; // 创建蚁群的次数

	    	/*if (ls_flag) {
				apply_local_search(vrpInstance);
			}	*/

            // 3.记录本次蚁群的信息，更新信息素
            update_statistics(vrpInstance);
            pheromone_trail_update();
            search_control_and_statistics();
            //force the ant colony thread to stop its execution

            // 4.如果本次线程执行创建蚁群次数超过300，就中断优化
            if (counter > 300) {
                isRunning = false;
            }

        }
        //System.out.println("Counter=" + counter + "; After terminating work in thread: best solution is >> No. of used vehicles=" + Ants.best_so_far_ant.usedVehicles + " total tours length=" + Ants.best_so_far_ant.total_tour_length);
    }

    //checks whether termination condition is met
    // 检查是否满足时间限制条件：从startTime到现在花费的时间是否超过了设定的最大时间长度
    static boolean termination_condition() {
        return Timer.elapsed_time() >= InOut.max_time;
    }

    /**
     * 在蚂蚁a中，判断将编号为city的城市，加入到编号为indexSalesman的路径末端，是否可行
     *
     * @param vrp
     * @param a
     * @param city：城市编号
     * @param beginService：city的开始服务时间
     * @param beginServiceDepot：仓库的开始服务时间
     * @param indexSalesman：路径编号
     * @return
     */
    static boolean isFeasible(VRPTW vrp, Ant a, int city, double beginService, double beginServiceDepot, int indexSalesman) {
        boolean ok = false;
        double currentQuantity;
        ArrayList<Request> reqList = vrp.getRequests();

        //check upper bound of the time window of the next customer to be visited &&
        //current capacity of the car && vehicle arrival time at the depot (the maximum total route time -> upper bound of the time window of the depot)
        currentQuantity = a.currentQuantity.get(indexSalesman) + reqList.get(city + 1).getDemand();
        if (beginService <= reqList.get(city + 1).getEndWindow() // 开始服务时间不晚于时间窗结束时间
                && currentQuantity <= vrp.getCapacity() // 满足车辆容量约束
                && beginServiceDepot <= reqList.get(0).getEndWindow()) { // 最终回到仓库的时间满足仓库的时间窗结束时间
            ok = true;
        }

//        以下代码没什么用
        if (ok == false) {
            if (beginService > reqList.get(city + 1).getEndWindow()) {
                //System.out.println("City " + city + ": End time window constraint violated");
            }
            if (currentQuantity > vrp.getCapacity()) {
                //System.out.println("City " + city + ": Vehicle capacity constraint violated");
            }
            if (beginServiceDepot > reqList.get(0).getEndWindow()) {
                //System.out.println("City " + city + ": Maximum total route time constraint violated");
            }
        }
        return ok;
    }

    //	计算mij的三个权重，用于nearest-neighbour heuristic中。其实是用来计算mij，在生成初始解的时候使用
    //generate the 3 weights to be used in the nearest-neighbour heuristic,
    // when computing an initial solution to the VRPTW problem
    static void generateInitialWeights() {
        double nr1, nr2;

        nr1 = Math.random();
        while (nr1 == 0.0) {
            nr1 = Math.random();
        }
        //weight for the distance between two nodes in the graph measure
        Ants.initialWeight1 = nr1;

        //weight for the time difference measure
        //nr2 should be in the range of (0, 1 - nr1)
        nr2 = Math.random() * (1 - nr1);
        Ants.initialWeight2 = nr2;

        //weight for the delivery urgency measure
        Ants.initialWeight3 = 1 - nr1 - nr2;
    }

    // 判断蚁群中的每个蚂蚁是否处理完了所有的城市节点
    //check if there is still an ant with left cities to visit
    static boolean isDone() {
        boolean done = true;

        for (int k = 0; k < Ants.n_ants; k++) {
            if (Ants.ants[k].toVisit > 0) {
                return false;
            }
        }

        return done;
    }

    // 将当前最优解的各条路径中的已经锁定的城市，添加到蚂蚁a的每条路径中。
    // add to the ant's solution the committed nodes from each tour of the best so far solution
    static void addCommitedNodes(Ant a, VRPTW instance) {
        int index, city, current_city;
        double distance, arrivalTime, beginService;
        ArrayList<Request> reqList = instance.getRequests();
        int startIndex = 1, pos;

        // 创建链表lastCommitedIndexes。用于存储当前最优解的每条路径中，最后锁定的城市节点的位置。
        ArrayList<Integer> lastCommitedIndexes = new ArrayList<Integer>();
        for (int indexTour = 0; indexTour < Ants.best_so_far_ant.usedVehicles; indexTour++) {
            pos = Controller.getLastCommitedPos(indexTour);
            lastCommitedIndexes.add(pos);
        }

        for (int i = 0; i < lastCommitedIndexes.size(); i++) { // 遍历路径
            // we have at least one committed node in the i-th tour (i.e. tour with index i)
            // 取出i路径的最后一个锁定城市的index（这是最后一个锁定城市在路径中的位置索引）
            index = lastCommitedIndexes.get(i);
            // 仅将非空路径复制为蚂蚁的路径
            // 如果在当前最优解中，路径i末端城市不是仓库，即这条路径不是空路径，就肯定存在锁定城市节点，可以执行操作
            if (index > 0) {
                // 1. 如果蚂蚁a的路径数量小于当前最优解的路径数量，则为蚂蚁a添加新路径
                // if the number of vehicles (tours) from the ant solution is less than the index of the
                // tour from the best so far solution, add new (empty) tours in the ant's solution
                // 这里为什么小于(i+1)而不是小于 i ，因为(a.usedVehicles)从1开始，而lastCommitedIndexes从0开始
                if (a.usedVehicles < (i + 1)) {
                    a.usedVehicles = i + 1;
                    for (int l = startIndex; l < a.usedVehicles; l++) {
                        a.tours.add(l, new ArrayList<Integer>());
                        a.tours.get(l).add(-1);
                        a.tour_lengths.add(l, 0.0);
                        a.currentQuantity.add(l, 0.0);
                        a.currentTime.add(l, 0.0);
                    }
                    startIndex = i + 1;
                }

                // 2.获取蚂蚁a路径i末端的城市编号current_city（其实这些蚂蚁都是重置后的，每条路径开始的位置是仓库）
                int lastPos = a.tours.get(i).size() - 1;
                current_city = a.tours.get(i).get(lastPos);
                current_city++; // 从路径取出来的城市编号是从 -1开始的，所以要+1

                // 3. 将锁定城市节点，添加到蚂蚁a的路径i中
                // add in the ant's i-th tour all the committed nodes from the i-th tour of the best so far solution
                for (int j = 1; j <= index; j++) {
                    city = Ants.best_so_far_ant.tours.get(i).get(j);

                    // 3.1 判断是否满足时间窗约束（应该是不存在违反时间窗约束的情况）
                    distance = VRPTW.instance.distance[current_city][city + 1];
                    arrivalTime = a.currentTime.get(i) + reqList.get(current_city).getServiceTime() + distance;
                    beginService = Math.max(arrivalTime, reqList.get(city + 1).getStartWindow());
                    if (beginService > reqList.get(city + 1).getEndWindow()) {
                        System.out.println("Method addCommitedNodes: solution infeasible..");
                    }

                    // 3.2 add committed node to the ant's tour
                    a.tours.get(i).add(j, city);
                    a.visited[city] = true;
                    a.toVisit--;
                    a.currentTime.set(i, beginService);
                    a.beginService[city + 1] = beginService;
                    a.currentQuantity.set(i, a.currentQuantity.get(i) + reqList.get(city + 1).getDemand());

                    current_city = city + 1;
                }
            }
        }
    }

    //check if there are any committed tours
    // (i.e. tours that contain at least one committed node that should be included in the ant's solution)
    static boolean checkCommitedTours() {
        boolean result = false;
        int lastPos;

        ArrayList<Integer> lastCommitedIndexes = new ArrayList<Integer>();
        for (int index = 0; index < Ants.best_so_far_ant.usedVehicles; index++) {
            lastPos = Controller.getLastCommitedPos(index);
            lastCommitedIndexes.add(lastPos);
        }

        for (int index : lastCommitedIndexes) {
            if (index > 0) {
                return true;
            }
        }

        return result;
    }

    /**
     * 构造解，构造每一次蚁群迭代生成的解
     * manage the solution construction phase
     * (construct a set of complete and closed tours, one for each vehicle)
     */
    static void construct_solutions(VRPTW instance) {
        int k; /* counter variable */
        int step = 0; /* counter of the number of construction steps */
        int values[] = new int[2]; // 存储最终的两个优化目标

        // 1. 重置所有蚂蚁
        /* Mark all cities as unvisited */
        for (k = 0; k < Ants.n_ants; k++) {
            Ants.ant_empty_memory(Ants.ants[k], instance);
        }

        // 2. 初始化每只蚂蚁的每条路径的第一个访问节点，即为每条路径设置初始仓库
        /* Place the ants on same initial city, which is the depot city */
        for (k = 0; k < Ants.n_ants; k++) {
            //Ants.place_ant(Ants.ants[k], step);
            for (int i = 0; i < Ants.ants[k].usedVehicles; i++) {
                // place each ant on the depot city, which is the start city of each tour
                // -1 is a special marker for the deport city, so that it's not be confused with the rest of the cities
                // all the rest of the cities are represented by integer values > 0
                Ants.ants[k].tours.get(i).add(-1); // 这里面用-1代表仓库的编号
            }
        }

        // 3. 用当前最优解，初始化每一次迭代生成的新解（可以把这一步理解为，通过当前最优解，初始化迭代一次得到的新蚁群）
        // initialize ant solution with the committed nodes (if any) from each tour of the best so far solution
        if (checkCommitedTours()) { // 如果当前最优解中存在已锁定的节点
            for (k = 0; k < Ants.n_ants; k++) {
                // 将当前所有蚂蚁的每条路径的每个锁定城市节点，添加到蚂蚁Ants.ants[k]的每条路径中
                addCommitedNodes(Ants.ants[k], instance);
                //System.out.println("After addCommitedNodes");
            }
        }

//		4. 每个蚂蚁都处理完所有的未处理城市请求（将未处理的请求城市放到路径末端，通过计算(v, s)）
        while (!isDone()) {
            for (k = 0; k < Ants.n_ants; k++) {
                if (Ants.ants[k].toVisit > 0) {

//					4.1 计算(v, s)，处理城市请求集合中的一个请求（找到最佳匹配“路径-城市”，并执行操作）
                    //choose for each ant in a probabilistic way by some type of roullette wheel selection
                    //which salesman to consider next, that will visit a city
                    //salesman = (int)(Math.random() * MTsp.m);
                    values = Ants.neighbour_choose_and_move_to_next(Ants.ants[k], instance);

//					4.2 更新局部信息素（蚂蚁每走一步，就更新这一步的信息素）
                    if (values[0] != -1) {
                        if (Ants.acs_flag)
                            Ants.local_acs_pheromone_update(Ants.ants[k], values[1]);
                    }
                }
            }
        }

        //System.out.println("After building tours");

//		5. 每只蚂蚁的每条路径最终回到仓库
        double longestTourLength;
        int idLongestTour = 0;
        for (k = 0; k < Ants.n_ants; k++) {
            InOut.noSolutions++; // 找到解的数量+1
            longestTourLength = Double.MIN_VALUE;
            for (int i = 0; i < Ants.ants[k].usedVehicles; i++) {
                step = Ants.ants[k].tours.get(i).size();
                Ants.ants[k].tours.get(i).add(step, -1);

                Ants.ants[k].tour_lengths.set(i, VRPTW.compute_tour_length_(Ants.ants[k].tours.get(i)));
                Ants.ants[k].total_tour_length += Ants.ants[k].tour_lengths.get(i);
                if (longestTourLength < Ants.ants[k].tour_lengths.get(i)) {
                    longestTourLength = Ants.ants[k].tour_lengths.get(i);
                    idLongestTour = i;
                }

                if (Ants.acs_flag)
                    Ants.local_acs_pheromone_update(Ants.ants[k], i);
            }
            Ants.ants[k].longest_tour_length = longestTourLength;
            Ants.ants[k].indexLongestTour = idLongestTour;
            //Ants.ants[k].total_tour_length = Tsp.compute_tour_lengths(Ants.ants[k].tours);
            Ants.ants[k].costObjectives[0] = Ants.ants[k].total_tour_length;
            Ants.ants[k].costObjectives[1] = Ants.computeToursAmplitude(Ants.ants[k]);
        }
        InOut.n_tours += (Ants.n_ants * Ants.ants[0].usedVehicles); //each ant constructs a complete and closed tour
    }

    /**
     * 实验开始，初始化变量，初始化蚁群信息素矩阵
     * initialize variables appropriately when starting a trial
     */
    static void init_try(VRPTW instance) {

        Timer.start_timers(); // 获取实验的开始时间
        InOut.time_used = Timer.elapsed_time();
        InOut.time_passed = InOut.time_used;
        int noAvailableNodes;

        // 1. 初始化静态参数
        /* Initialize variables concerning statistics etc. */
        InOut.n_tours = 1;
        InOut.iteration = 1;
        Ants.best_so_far_ant.total_tour_length = Double.MAX_VALUE;
        Ants.restart_best_ant.total_tour_length = Double.MAX_VALUE;
        InOut.found_best = 0;
        InOut.lambda = 0.05;

        // 2. 如果使用 as 优化,初始化信息素矩阵【未使用此算法】
        // Initialize the Pheromone trails, only if ACS is used, Ants.pheromones have to be initialized differently
        if (!(Ants.acs_flag)) {
            Ants.trail_0 = 1. / ((Ants.rho) * Ants.nn_tour(instance));
            /*
             * in the original papers on Ant System it is not exactly defined what the
             * initial value of the Ants.pheromones is. Here we set it to some
             * small constant, analogously as done in MAX-MIN Ant System.
             */
            Ants.init_pheromone_trails(Ants.trail_0);
        }

        // 3. 如果使用 acs 优化，初始化信息素矩阵。【本研究使用ACS算法】
        if (Ants.acs_flag) {
            noAvailableNodes = instance.getIdAvailableRequests().size();
            //if no cities are available except the depot, set the pheromone levels to a static value
            if (noAvailableNodes == 0) {
                Ants.trail_0 = 1.0;
            } else {
                Ants.trail_0 = 1. / ((double) (noAvailableNodes + 1) * (double) Ants.nn_tour(instance));
            }
            Ants.init_pheromone_trails(Ants.trail_0);
        }
        /* Calculate combined information Ants.pheromone times heuristic information */
        //Ants.compute_total_information();
    }

    // 对蚁群进行局部搜索（这个方法在程序中没有使用到）
    //apply to each solution constructed by a ant, a local search phase to further improve the solution
    //the local search procedure is composed of 2 operators applied sequentially in this order: 
    //relocate single/multiple route and exchange single/multiple route
    //as a result, all ants of the colony will have locally optimal tours
    static void apply_local_search(VRPTW instance) {
        for (int k = 0; k < Ants.n_ants; k++) {
            Ants.ants[k] = local_search(Ants.ants[k], instance);
        }
    }

    //对蚂蚁a进行局部搜索（重新定位算子和交换算子）
    //skip committed (defined) nodes when applying local search operators 
    static Ant local_search(Ant a, VRPTW instance) {
        //apply relocate multiple route local search operator
        a = relocateMultipleRoute(a, instance);
        //apply exchange multiple route local search operator
        a = exchangeMultipleRoute(a, instance);
        return a;
    }

    /**
     * 检查relocate操作的可行性
     *
     * @param a
     * @param vrp
     * @param indexTourSource：源路径
     * @param indexTourDestination：目标路径
     * @param i：抽出的城市在源路径中的位置
     * @param j：插入到目标路径中的位置
     * @return
     */
    static boolean checkFeasibleTourRelocationMultiple(Ant a, VRPTW vrp, int indexTourSource, int indexTourDestination, int i, int j) {
        boolean isFeasible = true;
        int city, previousCity, prevCity, nextCity, currentCity;
        double currentQuantity, arrivalTime, currentTime = 0.0, beginService, earliestTime, latestTime, distance;
        ArrayList<Request> reqList = vrp.getRequests();
        double value1, value2, value3, value4;

//        1. 检查是否满足，插入路径的载量约束
        city = a.tours.get(indexTourSource).get(i);
        currentQuantity = a.currentQuantity.get(indexTourDestination) + reqList.get(city + 1).getDemand();
        if (currentQuantity > vrp.getCapacity()) {
            return false;
        }

//        2. 检查时间窗约束
//          2.1 检查源路径的时间窗约束
        // check time window constraints in source tour
        for (int pos = i + 1; pos < a.tours.get(indexTourSource).size(); pos++) {
            if (pos == (i + 1)) {
                prevCity = a.tours.get(indexTourSource).get(pos - 2); // 源路径中，抽出城市前面的城市
                currentCity = a.tours.get(indexTourSource).get(pos);
                currentTime = a.beginService[prevCity + 1];
            } else {
                prevCity = a.tours.get(indexTourSource).get(pos - 1);
                currentCity = a.tours.get(indexTourSource).get(pos);
            }
            distance = VRPTW.instance.distance[prevCity + 1][currentCity + 1];
            arrivalTime = currentTime + reqList.get(prevCity + 1).getServiceTime() + distance;
            beginService = Math.max(arrivalTime, reqList.get(currentCity + 1).getStartWindow());
            if (beginService > reqList.get(currentCity + 1).getEndWindow()) {
                return false;
            }
            currentTime = beginService;
        }
		
		/*previousCity = a.tours.get(indexTourDestination).get(j - 1);
        nextCity = a.tours.get(indexTourDestination).get(j);
    	
    	arrivalTime = a.beginService[previousCity + 1] + reqList.get(previousCity + 1).getServiceTime() + VRPTW.instance.distance[previousCity + 1][city + 1]; 
    	beginService = Math.max(arrivalTime, reqList.get(city + 1).getStartWindow());
    	if (beginService > reqList.get(city + 1).getEndWindow()) {
    		return false;
    	}
    	
    	value1 = new Double(reqList.get(city + 1).getStartWindow());
    	//value2 = a.earliestTime.get(indexTour).get(previousPos) + VRPTW.instance.distance[previousCity + 1][customer + 1];
    	value2 = a.earliestTime.get(indexTourDestination).get(j - 1) + VRPTW.instance.distance[previousCity + 1][city + 1] + reqList.get(previousCity + 1).getServiceTime();
    	earliestTime = Math.max(value1, value2);
    	value3 = new Double(reqList.get(city + 1).getEndWindow());
    	//value4 = a.latestTime.get(indexTour).get(nextPos) - VRPTW.instance.distance[customer + 1][nextCity + 1];
    	value4 = a.latestTime.get(indexTourDestination).get(j) - VRPTW.instance.distance[city + 1][nextCity + 1] - reqList.get(city + 1).getServiceTime();
    	latestTime = Math.min(value3, value4);
    	
		if (earliestTime > latestTime) {
			return false;
		}*/

//        2.2 检查目标路径的时间窗约束
        //check time window constraints in destination tour
//          2.2.1 prevCity--->city
        previousCity = a.tours.get(indexTourDestination).get(j - 1);
        nextCity = a.tours.get(indexTourDestination).get(j);

        arrivalTime = a.beginService[previousCity + 1] + reqList.get(previousCity + 1).getServiceTime() + VRPTW.instance.distance[previousCity + 1][city + 1];
        beginService = Math.max(arrivalTime, reqList.get(city + 1).getStartWindow());
        if (beginService > reqList.get(city + 1).getEndWindow()) {
            return false;
        }
        currentTime = beginService;

//        2.2.2 city--->nextCity
        arrivalTime = currentTime + reqList.get(city + 1).getServiceTime() + VRPTW.instance.distance[city + 1][nextCity + 1];
        beginService = Math.max(arrivalTime, reqList.get(nextCity + 1).getStartWindow());
        if (beginService > reqList.get(nextCity + 1).getEndWindow()) {
            return false;
        }
        currentTime = beginService;

//        2.2.3 city--->
        for (int pos = j + 1; pos < a.tours.get(indexTourDestination).size(); pos++) {
            prevCity = a.tours.get(indexTourDestination).get(pos - 1);
            currentCity = a.tours.get(indexTourDestination).get(pos);
            distance = VRPTW.instance.distance[prevCity + 1][currentCity + 1];
            arrivalTime = currentTime + reqList.get(prevCity + 1).getServiceTime() + distance;
            beginService = Math.max(arrivalTime, reqList.get(currentCity + 1).getStartWindow());
            if (beginService > reqList.get(currentCity + 1).getEndWindow()) {
                return false;
            }
            currentTime = beginService;
        }

        return isFeasible;
    }

    /**
     * 更新开始服务时间和当前时间（更新的都是执行relocate操作的位置后面的城市序列）
     *
     * @param a
     * @param vrp
     * @param indexTourSource
     * @param indexTourDestination
     * @param i
     * @param j
     */
    static void updateBeginServiceRelocationMultiple(Ant a, VRPTW vrp, int indexTourSource, int indexTourDestination, int i, int j) {
        int currentCity, prevCity;
        double currentTime = 0.0;
        double distance, arrivalTime, beginService = 0.0;
        ArrayList<Request> reqList = vrp.getRequests();

//        1. update of begin service times for the source tour
        for (int pos = i; pos < a.tours.get(indexTourSource).size() - 1; pos++) {
            prevCity = a.tours.get(indexTourSource).get(pos - 1);
            currentCity = a.tours.get(indexTourSource).get(pos);
            if (pos == i) {
                currentTime = a.beginService[prevCity + 1];
            }
            distance = VRPTW.instance.distance[prevCity + 1][currentCity + 1];
            arrivalTime = currentTime + reqList.get(prevCity + 1).getServiceTime() + distance;
            beginService = Math.max(arrivalTime, reqList.get(currentCity + 1).getStartWindow());
            currentTime = beginService;
            a.beginService[currentCity + 1] = beginService;
            if (beginService > reqList.get(currentCity + 1).getEndWindow()) {
                System.out.println("Relocation Multiple indexTourSource: Unfeasible solution..");
            }
        }
        a.currentTime.set(indexTourSource, beginService); // 路径末端城市的开始服务时间即为路径的当前时间

//        2. update of begin service times for the destination tour
        for (int pos = j; pos < a.tours.get(indexTourDestination).size() - 1; pos++) {
            prevCity = a.tours.get(indexTourDestination).get(pos - 1);
            currentCity = a.tours.get(indexTourDestination).get(pos);
            if (pos == j) {
                currentTime = a.beginService[prevCity + 1];
            }
            distance = VRPTW.instance.distance[prevCity + 1][currentCity + 1];
            arrivalTime = currentTime + reqList.get(prevCity + 1).getServiceTime() + distance;
            beginService = Math.max(arrivalTime, reqList.get(currentCity + 1).getStartWindow());
            currentTime = beginService;
            a.beginService[currentCity + 1] = beginService;
            if (beginService > reqList.get(currentCity + 1).getEndWindow()) {
                System.out.println("Relocation Multiple indexTourDestination: Unfeasible solution..");
            }
        }
        a.currentTime.set(indexTourDestination, beginService);

    }

    //skip committed (defined) nodes
    //relocateMultipleRoute is performed only once and the best improvement (which minimizes most the total traveled distance) is applied
    //	对蚂蚁a执行多次尝试的relocate操作，找到最优的那个relocate操作，记录下来，并返回。
    //已经指定好路径的请求城市是不能再更改的，所以只能是从最后一个指定好的城市的下一个城市开始执行操作。
    static Ant relocateMultipleRoute(Ant a, VRPTW instance) {
        boolean feasible = false;
        int city, sourcePrevCity, sourceNextCity = -2, destinationPrevCity, destinationNextCity;
        int startIndexSource, startIndexDestination;
        double newQuantity1, newQuantity2, newDistance1, newDistance2, newTotalDistance;
        ArrayList<Request> reqList = instance.getRequests();
        int lastPos;

//        1. 创建蚂蚁bestImprovedAnt
        Ant bestImprovedAnt = new Ant();
        bestImprovedAnt.tours = new ArrayList();
        bestImprovedAnt.tour_lengths = new ArrayList<Double>();
        bestImprovedAnt.beginService = new double[VRPTW.n + 1];
        bestImprovedAnt.currentTime = new ArrayList<Double>();
        bestImprovedAnt.currentQuantity = new ArrayList<Double>();
        bestImprovedAnt.usedVehicles = 1;
        for (int j = 0; j < bestImprovedAnt.usedVehicles; j++) {
            bestImprovedAnt.tours.add(j, new ArrayList<Integer>());
            bestImprovedAnt.tour_lengths.add(j, 0.0);
        }
        bestImprovedAnt.visited = new boolean[VRPTW.n];
        //the another node is the depot, which is by default visited by each salesman and added in its tour
        bestImprovedAnt.toVisit = instance.getIdAvailableRequests().size();
        bestImprovedAnt.costObjectives = new double[2];
        for (int indexObj = 0; indexObj < 2; indexObj++) {
            bestImprovedAnt.costObjectives[indexObj] = 0;
        }
        bestImprovedAnt.earliestTime = new ArrayList(bestImprovedAnt.usedVehicles);
        bestImprovedAnt.latestTime = new ArrayList(bestImprovedAnt.usedVehicles);

//        2. 创建蚂蚁temp（相当于一个中间变量）
        Ant temp = new Ant();
        temp.tours = new ArrayList();
        temp.tour_lengths = new ArrayList<Double>();
        temp.beginService = new double[VRPTW.n + 1];
        temp.currentTime = new ArrayList<Double>();
        temp.currentQuantity = new ArrayList<Double>();
        temp.usedVehicles = 1;
        for (int j = 0; j < temp.usedVehicles; j++) {
            temp.tours.add(j, new ArrayList<Integer>());
            temp.tour_lengths.add(j, 0.0);
        }
        temp.visited = new boolean[VRPTW.n];
        //the another node is the depot, which is by default visited by each salesman and added in its tour
        temp.toVisit = instance.getIdAvailableRequests().size();
        temp.costObjectives = new double[2];
        for (int indexObj = 0; indexObj < 2; indexObj++) {
            temp.costObjectives[indexObj] = 0;
        }
        temp.earliestTime = new ArrayList(temp.usedVehicles);
        temp.latestTime = new ArrayList(temp.usedVehicles);

        Ants.copy_from_to(a, bestImprovedAnt, instance);
        Ants.copy_from_to(a, temp, instance);

        ArrayList<Integer> lastCommitedIndexes = new ArrayList<Integer>();
        for (int index = 0; index < Ants.best_so_far_ant.usedVehicles; index++) {
            lastPos = Controller.getLastCommitedPos(index);
            lastCommitedIndexes.add(lastPos);
        }

//        3. 遍历尝试relocate方法，找到最佳的relocate操作
//           分别遍历源路径和目标路径，
        for (int indexTourSource = 0; indexTourSource < a.usedVehicles; indexTourSource++) {
            for (int indexTourDestination = 0; indexTourDestination < a.usedVehicles; indexTourDestination++) {
                if (indexTourSource != indexTourDestination) {
                    // 已经锁定的城市是不能再更改的，所以只能是从锁定城市的下一个城市开始执行操作。

//                    3.1 index of the element to be moved/relocated（得到源路径的开始索引）
                    if (indexTourSource > lastCommitedIndexes.size() - 1) {
                        startIndexSource = 1;
                    } else {
                        startIndexSource = lastCommitedIndexes.get(indexTourSource) + 1;
                    }


//                    3.2 index of the relocation's destination（得到目标路径的开始索引）
                    if (indexTourDestination > lastCommitedIndexes.size() - 1) {
                        startIndexDestination = 1;
                    } else {
                        startIndexDestination = lastCommitedIndexes.get(indexTourDestination) + 1;
                    }

//                    3.3 根据前面得到的开始索引，分别遍历源头路径和目标路径，寻找最佳relocate
                    for (int i = startIndexSource; i < a.tours.get(indexTourSource).size() - 1; i++) {
                        for (int j = startIndexDestination; j < a.tours.get(indexTourDestination).size(); j++) {
                            //检查relocate操作的可行性
                            //check if results a feasible solution (i.e. no time window constraint is violated)
                            feasible = checkFeasibleTourRelocationMultiple(temp, instance, indexTourSource, indexTourDestination, i, j);
                            if (feasible) {
//                                3.3.1 获取变动城市的编号，并在路径中修改
                                //obtain the neighbour solution corresponding to the relocation operator
                                city = temp.tours.get(indexTourSource).get(i);
                                temp.tours.get(indexTourSource).remove(i);
                                temp.tours.get(indexTourDestination).add(j, city);

//                                3.3.2 更新路径载量
                                newQuantity1 = temp.currentQuantity.get(indexTourSource) - reqList.get(city + 1).getDemand();
                                temp.currentQuantity.set(indexTourSource, newQuantity1);
                                newQuantity2 = temp.currentQuantity.get(indexTourDestination) + reqList.get(city + 1).getDemand();
                                temp.currentQuantity.set(indexTourDestination, newQuantity2);

//                                3.3.3 更新开始服务时间和路径的当前时间
                                //update the begin service times of the nodes from the source and destination tours of the obtained neighbour solution
                                //also update the current time of the source and destination tours
                                updateBeginServiceRelocationMultiple(temp, instance, indexTourSource, indexTourDestination, i, j);

//                                3.3.4 更新蚂蚁的总路程，源路径路程和目标路径的路程
                                //update total traveled distance and lengths of source and destination tours
                                sourcePrevCity = temp.tours.get(indexTourSource).get(i - 1);
                                sourceNextCity = temp.tours.get(indexTourSource).get(i);
                                newDistance1 = temp.tour_lengths.get(indexTourSource) - VRPTW.instance.distance[sourcePrevCity + 1][city + 1] - VRPTW.instance.distance[city + 1][sourceNextCity + 1] + VRPTW.instance.distance[sourcePrevCity + 1][sourceNextCity + 1];

                                destinationPrevCity = temp.tours.get(indexTourDestination).get(j - 1);
                                destinationNextCity = temp.tours.get(indexTourDestination).get(j + 1);
                                newDistance2 = temp.tour_lengths.get(indexTourDestination) - VRPTW.instance.distance[destinationPrevCity + 1][destinationNextCity + 1] + VRPTW.instance.distance[destinationPrevCity + 1][city + 1] + VRPTW.instance.distance[city + 1][destinationNextCity + 1];

                                newTotalDistance = temp.total_tour_length - temp.tour_lengths.get(indexTourSource) - temp.tour_lengths.get(indexTourDestination) + newDistance1 + newDistance2;
                                temp.total_tour_length = newTotalDistance;
                                temp.tour_lengths.set(indexTourSource, newDistance1);
                                temp.tour_lengths.set(indexTourDestination, newDistance2);

//                                3.3.5 删除空路径（即删除只有出发仓库和终点仓库的路径）
                                //if the source tour becomes empty (no city is visited except the depot), remove this empty tour
                                if (temp.tours.get(indexTourSource).size() == 2 && temp.tours.get(indexTourSource).get(0) == -1 && temp.tours.get(indexTourSource).get(1) == -1) {
                                    temp.tours.remove(indexTourSource);
                                    temp.usedVehicles--;
                                }

//                                3.3.6 如果本次relocate得到的值优于目标最优的，则更新bestImprovedAnt
//                                （这里没有考虑优化目标的优先级，只要满足一个优化即可，目的在于尽可能多在邻域搜索）
                                //if some improvement is obtained in the total traveled distance
                                if ((temp.total_tour_length < bestImprovedAnt.total_tour_length)
                                        || (temp.usedVehicles < bestImprovedAnt.usedVehicles)) {
                                    Ants.copy_from_to(temp, bestImprovedAnt, instance);
                                }

//                                3.3.7 将temp格式化到原来的状态，即使它消除上面的relocate操作，以便以后的操作。
                                //restore previous solution constructed by ant
                                Ants.copy_from_to(a, temp, instance);
                            }
                        }
                    }
                }
            }
        }
        return bestImprovedAnt;
    }

    // 寻找遍历城市数量最少的路径
    //find the index of the tour having the smallest number of visited nodes (cities/customers)
    static int findShortestTour(Ant a) {
        int indexTour = 0;
        int min = Integer.MAX_VALUE;

        for (int i = 0; i < a.usedVehicles; i++) {
            if (min > a.tours.get(i).size()) {
                min = a.tours.get(i).size();
                indexTour = i;
            }
        }
        return indexTour;
    }

    //    有迭代的relocate算子的实现，返回多次迭代得到的最佳蚂蚁
//    relocateMultipleRoute可以看做是一次迭代操作，尝试找到本次迭代的最佳蚂蚁
//    本函数在relocateMultipleRoute的基础上套了一个while循环，可以进行多次迭代操作
//    在比较relocateMultipleRoute得到的结果时，考虑了优化目标的优先级

    /**
     * 先假设这是一次局部搜索
     * skip committed (defined) nodes
     * relocateMultipleRouteIterated is performed multiple times until no further improvement
     * (which minimizes most the total traveled distance or reduces the number of used vehicles) is possible
     */
    static Ant relocateMultipleRouteIterated(Ant a, VRPTW instance) {
        boolean feasible = false;
        int city, sourcePrevCity, sourceNextCity = -2, destinationPrevCity, destinationNextCity;
        int startIndexSource, startIndexDestination;
        double newQuantity1, newQuantity2, newDistance1, newDistance2, newTotalDistance;
        ArrayList<Request> reqList = instance.getRequests();
        boolean foundImprovement = true, isValid;
        int lastPos;
        double tempNo = Math.pow(10, 10);
        double round1, round2;

//        1. 定义蚂蚁improvedAnt
        Ant improvedAnt = new Ant();
        improvedAnt.tours = new ArrayList();
        improvedAnt.tour_lengths = new ArrayList<Double>();
        improvedAnt.beginService = new double[VRPTW.n + 1];
        improvedAnt.currentTime = new ArrayList<Double>();
        improvedAnt.currentQuantity = new ArrayList<Double>();
        improvedAnt.usedVehicles = 1;
        for (int j = 0; j < improvedAnt.usedVehicles; j++) {
            improvedAnt.tours.add(j, new ArrayList<Integer>());
            improvedAnt.tour_lengths.add(j, 0.0);
        }
        improvedAnt.visited = new boolean[VRPTW.n];
        //the another node is the depot, which is by default visited by each salesman and added in its tour
        improvedAnt.toVisit = instance.getIdAvailableRequests().size();
        improvedAnt.costObjectives = new double[2];
        for (int indexObj = 0; indexObj < 2; indexObj++) {
            improvedAnt.costObjectives[indexObj] = 0;
        }
        improvedAnt.earliestTime = new ArrayList(improvedAnt.usedVehicles);
        improvedAnt.latestTime = new ArrayList(improvedAnt.usedVehicles);

//        2. 定义蚂蚁temp
        Ant temp = new Ant();
        temp.tours = new ArrayList();
        temp.tour_lengths = new ArrayList<Double>();
        temp.beginService = new double[VRPTW.n + 1];
        temp.currentTime = new ArrayList<Double>();
        temp.currentQuantity = new ArrayList<Double>();
        temp.usedVehicles = 1;
        for (int j = 0; j < temp.usedVehicles; j++) {
            temp.tours.add(j, new ArrayList<Integer>());
            temp.tour_lengths.add(j, 0.0);
        }
        temp.visited = new boolean[VRPTW.n];
        //the another node is the depot, which is by default visited by each salesman and added in its tour
        temp.toVisit = instance.getIdAvailableRequests().size();
        temp.costObjectives = new double[2];
        for (int indexObj = 0; indexObj < 2; indexObj++) {
            temp.costObjectives[indexObj] = 0;
        }
        temp.earliestTime = new ArrayList(temp.usedVehicles);
        temp.latestTime = new ArrayList(temp.usedVehicles);

//        3. 把蚂蚁a复制到，improvedAnt蚂蚁和temp蚂蚁
        Ants.copy_from_to(a, improvedAnt, instance);
        Ants.copy_from_to(a, temp, instance);

//        4. 获取每条路径的最后一个锁定节点的位置，作为relocate操作时每条路径开始的索引
        ArrayList<Integer> lastCommitedIndexes = new ArrayList<Integer>();
        for (int index = 0; index < Ants.best_so_far_ant.usedVehicles; index++) {
            lastPos = Controller.getLastCommitedPos(index);
            lastCommitedIndexes.add(lastPos);
        }

        int count = 0; // 记录迭代次数
//        5. 如果在一次遍历每条路径的每个位置的relocate操作中，还能找到改进的解，则继续进行迭代，否则跳出迭代。
        while (foundImprovement) { // 是否还存在优化空间
            //System.out.println("foundImprovement = " + foundImprovement + " count = " + count);
            foundImprovement = false;

            count++;
            if (count > 100) {
                System.out.println("Inside relocateMultipleRouteIterated; count=" + count);
            }

            Ants.copy_from_to(improvedAnt, a, instance);
            Ants.copy_from_to(improvedAnt, temp, instance);

            // 遍历每条可能的源路径和目标路径
            for (int indexTourSource = 0; indexTourSource < temp.usedVehicles; indexTourSource++) {
                for (int indexTourDestination = 0; indexTourDestination < temp.usedVehicles; indexTourDestination++) {
                    if (indexTourSource != indexTourDestination) {
                        //index of the element to be moved/relocated
                        if (indexTourSource > lastCommitedIndexes.size() - 1) {
                            startIndexSource = 1;
                        } else {
                            startIndexSource = lastCommitedIndexes.get(indexTourSource) + 1;
                        }

                        //index of the relocation's destination
                        if (indexTourDestination > lastCommitedIndexes.size() - 1) {
                            startIndexDestination = 1;
                        } else {
                            startIndexDestination = lastCommitedIndexes.get(indexTourDestination) + 1;
                        }

                        // 遍历源路径和目标路径的每个位置
                        for (int i = startIndexSource; i < temp.tours.get(indexTourSource).size() - 1; i++) {
                            for (int j = startIndexDestination; j < temp.tours.get(indexTourDestination).size(); j++) {
                                //check if results a feasible solution (i.e. no time window constraint is violated)
                                feasible = checkFeasibleTourRelocationMultiple(temp, instance, indexTourSource, indexTourDestination, i, j);
                                if (feasible) {
                                    //obtain the neighbour solution corresponding to the relocation operator
                                    city = temp.tours.get(indexTourSource).get(i);
                                    temp.tours.get(indexTourSource).remove(i);
                                    temp.tours.get(indexTourDestination).add(j, city);
								    
								    /*isValid = Utilities.checkFeasibility(temp, instance, false);
						    	    if (!isValid) {
						    	    	System.out.println("Inside relocateMultipleRouteIterated: The resulted solution is not valid (feasible)..");
						    	    }*/

                                    newQuantity1 = temp.currentQuantity.get(indexTourSource) - reqList.get(city + 1).getDemand();
                                    temp.currentQuantity.set(indexTourSource, newQuantity1);
                                    newQuantity2 = temp.currentQuantity.get(indexTourDestination) + reqList.get(city + 1).getDemand();
                                    temp.currentQuantity.set(indexTourDestination, newQuantity2);

                                    // update the begin service times of the nodes from the source and destination tours of the obtained neighbour solution
                                    // also update the current time of the source and destination tours
                                    updateBeginServiceRelocationMultiple(temp, instance, indexTourSource, indexTourDestination, i, j);

                                    //update total traveled distance and lengths of source and destination tours
                                    sourcePrevCity = temp.tours.get(indexTourSource).get(i - 1);
                                    sourceNextCity = temp.tours.get(indexTourSource).get(i);
                                    newDistance1 = temp.tour_lengths.get(indexTourSource) - VRPTW.instance.distance[sourcePrevCity + 1][city + 1] - VRPTW.instance.distance[city + 1][sourceNextCity + 1] + VRPTW.instance.distance[sourcePrevCity + 1][sourceNextCity + 1];

                                    destinationPrevCity = temp.tours.get(indexTourDestination).get(j - 1);
                                    destinationNextCity = temp.tours.get(indexTourDestination).get(j + 1);
                                    newDistance2 = temp.tour_lengths.get(indexTourDestination) - VRPTW.instance.distance[destinationPrevCity + 1][destinationNextCity + 1] + VRPTW.instance.distance[destinationPrevCity + 1][city + 1] + VRPTW.instance.distance[city + 1][destinationNextCity + 1];

                                    newTotalDistance = temp.total_tour_length - temp.tour_lengths.get(indexTourSource) - temp.tour_lengths.get(indexTourDestination) + newDistance1 + newDistance2;
                                    temp.total_tour_length = newTotalDistance;
                                    temp.tour_lengths.set(indexTourSource, newDistance1);
                                    temp.tour_lengths.set(indexTourDestination, newDistance2);

                                    //if the source tour becomes empty (no city is visited except the depot), remove this empty tour
                                    if (temp.tours.get(indexTourSource).size() == 2 && temp.tours.get(indexTourSource).get(0) == -1 && temp.tours.get(indexTourSource).get(1) == -1) {
                                        //System.out.println("Reducing with 1 the number of used vehicles");
                                        temp.tours.remove(indexTourSource);
                                        temp.tour_lengths.remove(indexTourSource);
                                        temp.currentQuantity.remove(indexTourSource);
                                        temp.currentTime.remove(indexTourSource);
                                        temp.usedVehicles--;
                                    }

                                    //performing the rounding of the two numbers up to 10 decimals so that in the
                                    //comparison of the 2 double values to consider only the first 10 most significant decimals
                                    round1 = Math.round(temp.total_tour_length * tempNo) / tempNo;
                                    round2 = Math.round(improvedAnt.total_tour_length * tempNo) / tempNo;
                                    //if some improvement is obtained in the total traveled distance
                                    // 注意优先级：车辆数量>总路程长度
                                    if (((round1 < round2) && (temp.usedVehicles == improvedAnt.usedVehicles))
                                            || (temp.usedVehicles < improvedAnt.usedVehicles)) {
                                        Ants.copy_from_to(temp, improvedAnt, instance);
                                        foundImprovement = true;
                                    }

                                    //restore previous solution constructed by ant
                                    Ants.copy_from_to(a, temp, instance);
                                }
                            }
                        }
                    }
                }
            }
        }
        return improvedAnt;
    }

    //    将城市节点最少的路径中的城市，插入到其他的路径中。以此来尽可能降低配送车辆的数量，优化解。（跟上面那个方法意思差不多，就不写注释了）
//    这也是一个重复迭代的过程，可能会执行很多次的relocate操作，直到不能找到更加优秀的解为止
    //skip committed (defined) nodes
    //relocateMultipleRouteIterated is performed multiple times until no further improvement (which minimizes most the
    //total traveled distance or reduces the number of used vehicles) is possible
    //try to relocate nodes from the tour having the minimum number of visited nodes, in an attempt
    //to reduce (minimize) the number of tours (i.e. used vehicles)
    static Ant relocateMultipleRouteIteratedShortest(Ant a, VRPTW instance) {
        boolean feasible = false;
        int city, sourcePrevCity, sourceNextCity = -2, destinationPrevCity, destinationNextCity;
        int startIndexSource, startIndexDestination;
        double newQuantity1, newQuantity2, newDistance1, newDistance2, newTotalDistance;
        ArrayList<Request> reqList = instance.getRequests();
        boolean foundImprovement = true;
        int indexTourSource, lastPos;

        Ant improvedAnt = new Ant();
        improvedAnt.tours = new ArrayList();
        improvedAnt.tour_lengths = new ArrayList<Double>();
        improvedAnt.beginService = new double[VRPTW.n + 1];
        improvedAnt.currentTime = new ArrayList<Double>();
        improvedAnt.currentQuantity = new ArrayList<Double>();
        improvedAnt.usedVehicles = 1;
        for (int j = 0; j < improvedAnt.usedVehicles; j++) {
            improvedAnt.tours.add(j, new ArrayList<Integer>());
            improvedAnt.tour_lengths.add(j, 0.0);
        }
        improvedAnt.visited = new boolean[VRPTW.n];
        //the another node is the depot, which is by default visited by each salesman and added in its tour
        improvedAnt.toVisit = instance.getIdAvailableRequests().size();
        improvedAnt.costObjectives = new double[2];
        for (int indexObj = 0; indexObj < 2; indexObj++) {
            improvedAnt.costObjectives[indexObj] = 0;
        }
        improvedAnt.earliestTime = new ArrayList(improvedAnt.usedVehicles);
        improvedAnt.latestTime = new ArrayList(improvedAnt.usedVehicles);

        Ant temp = new Ant();
        temp.tours = new ArrayList();
        temp.tour_lengths = new ArrayList<Double>();
        temp.beginService = new double[VRPTW.n + 1];
        temp.currentTime = new ArrayList<Double>();
        temp.currentQuantity = new ArrayList<Double>();
        temp.usedVehicles = 1;
        for (int j = 0; j < temp.usedVehicles; j++) {
            temp.tours.add(j, new ArrayList<Integer>());
            temp.tour_lengths.add(j, 0.0);
        }
        temp.visited = new boolean[VRPTW.n];
        //the another node is the depot, which is by default visited by each salesman and added in its tour
        temp.toVisit = instance.getIdAvailableRequests().size();
        temp.costObjectives = new double[2];
        for (int indexObj = 0; indexObj < 2; indexObj++) {
            temp.costObjectives[indexObj] = 0;
        }
        temp.earliestTime = new ArrayList(temp.usedVehicles);
        temp.latestTime = new ArrayList(temp.usedVehicles);

        Ants.copy_from_to(a, improvedAnt, instance);
        Ants.copy_from_to(a, temp, instance);

        ArrayList<Integer> lastCommitedIndexes = new ArrayList<Integer>();
        for (int index = 0; index < Ants.best_so_far_ant.usedVehicles; index++) {
            lastPos = Controller.getLastCommitedPos(index);
            lastCommitedIndexes.add(lastPos);
        }

        while (foundImprovement) {
            foundImprovement = false;

            Ants.copy_from_to(improvedAnt, a, instance);
            Ants.copy_from_to(a, temp, instance);

            indexTourSource = findShortestTour(a);
            for (int indexTourDestination = 0; indexTourDestination < a.usedVehicles; indexTourDestination++) {
                if (indexTourSource != indexTourDestination) {
                    //index of the element to be moved/relocated
                    if (indexTourSource > lastCommitedIndexes.size() - 1) {
                        startIndexSource = 1;
                    } else {
                        startIndexSource = lastCommitedIndexes.get(indexTourSource) + 1;
                    }

                    //index of the relocation's destination
                    if (indexTourDestination > lastCommitedIndexes.size() - 1) {
                        startIndexDestination = 1;
                    } else {
                        startIndexDestination = lastCommitedIndexes.get(indexTourDestination) + 1;
                    }
                    for (int i = startIndexSource; i < a.tours.get(indexTourSource).size() - 1; i++) {
                        for (int j = startIndexDestination; j < a.tours.get(indexTourDestination).size(); j++) {
                            //check if results a feasible solution (i.e. no time window constraint is violated)
                            feasible = checkFeasibleTourRelocationMultiple(temp, instance, indexTourSource, indexTourDestination, i, j);
                            if (feasible) {
                                //obtain the neighbour solution corresponding to the relocation operator
                                city = temp.tours.get(indexTourSource).get(i);
                                temp.tours.get(indexTourSource).remove(i);
                                temp.tours.get(indexTourDestination).add(j, city);

                                newQuantity1 = temp.currentQuantity.get(indexTourSource) - reqList.get(city + 1).getDemand();
                                temp.currentQuantity.set(indexTourSource, newQuantity1);
                                newQuantity2 = temp.currentQuantity.get(indexTourDestination) + reqList.get(city + 1).getDemand();
                                temp.currentQuantity.set(indexTourDestination, newQuantity2);

                                //update the begin service times of the nodes from the source and destination tours of the obtained neighbour solution
                                //also update the current time of the source and destination tours
                                updateBeginServiceRelocationMultiple(temp, instance, indexTourSource, indexTourDestination, i, j);

                                //update total traveled distance and lengths of source and destination tours
                                sourcePrevCity = temp.tours.get(indexTourSource).get(i - 1);
                                sourceNextCity = temp.tours.get(indexTourSource).get(i);
                                newDistance1 = temp.tour_lengths.get(indexTourSource) - VRPTW.instance.distance[sourcePrevCity + 1][city + 1] - VRPTW.instance.distance[city + 1][sourceNextCity + 1] + VRPTW.instance.distance[sourcePrevCity + 1][sourceNextCity + 1];

                                destinationPrevCity = temp.tours.get(indexTourDestination).get(j - 1);
                                destinationNextCity = temp.tours.get(indexTourDestination).get(j + 1);
                                newDistance2 = temp.tour_lengths.get(indexTourDestination) - VRPTW.instance.distance[destinationPrevCity + 1][destinationNextCity + 1] + VRPTW.instance.distance[destinationPrevCity + 1][city + 1] + VRPTW.instance.distance[city + 1][destinationNextCity + 1];

                                newTotalDistance = temp.total_tour_length - temp.tour_lengths.get(indexTourSource) - temp.tour_lengths.get(indexTourDestination) + newDistance1 + newDistance2;
                                temp.total_tour_length = newTotalDistance;
                                temp.tour_lengths.set(indexTourSource, newDistance1);
                                temp.tour_lengths.set(indexTourDestination, newDistance2);

                                //if the source tour becomes empty (no city is visited except the depot), remove this empty tour
                                if (temp.tours.get(indexTourSource).size() == 2 && temp.tours.get(indexTourSource).get(0) == -1 && temp.tours.get(indexTourSource).get(1) == -1) {
                                    temp.tours.remove(indexTourSource);
                                    temp.usedVehicles--;
                                }

                                //if some improvement is obtained in the total traveled distance
                                if (((temp.total_tour_length < improvedAnt.total_tour_length) && (temp.usedVehicles == improvedAnt.usedVehicles))
                                        || (temp.usedVehicles < improvedAnt.usedVehicles)) {
                                    Ants.copy_from_to(temp, improvedAnt, instance);
                                    foundImprovement = true;
                                }

                                //restore previous solution constructed by ant
                                Ants.copy_from_to(a, temp, instance);
                            }
                        }
                    }
                }
            }
        }
        return improvedAnt;
    }

    /**
     * exchang算子操作的可行性
     * 判断：将路径indexTourSource的第i个城市与路径indexTourDestination的第j个城市交换是否可行
     */
    static boolean checkFeasibleTourExchangeMultiple(Ant a, VRPTW vrp, int indexTourSource, int indexTourDestination, int i, int j) {
        boolean isFeasible = true;
        int currentCity, prevCity, city1, city2;
        double currentTime = 0.0;
        double distance, arrivalTime, beginService, currentQuantity;
        ArrayList<Request> reqList = vrp.getRequests();

//        1. 检查源路径和目标路径的载量限制
        //check vehicle capacity tour constraints for source and destination tours
        city1 = a.tours.get(indexTourSource).get(i);
        city2 = a.tours.get(indexTourDestination).get(j);
        currentQuantity = a.currentQuantity.get(indexTourSource) - reqList.get(city1 + 1).getDemand() + reqList.get(city2 + 1).getDemand();
        if (currentQuantity > vrp.getCapacity()) {
            return false;
        }
        currentQuantity = a.currentQuantity.get(indexTourDestination) - reqList.get(city2 + 1).getDemand() + reqList.get(city1 + 1).getDemand();
        if (currentQuantity > vrp.getCapacity()) {
            return false;
        }

//        2. 检查原路径的时间窗约束
        //check feasibility for source tour regarding time windows constraints
        for (int pos = i; pos < a.tours.get(indexTourSource).size(); pos++) {
            if (pos == i) {
                prevCity = a.tours.get(indexTourSource).get(pos - 1);
                currentCity = a.tours.get(indexTourDestination).get(j);
                currentTime = a.beginService[prevCity + 1];
            } else if (pos == (i + 1)) {
                prevCity = a.tours.get(indexTourDestination).get(j);
                currentCity = a.tours.get(indexTourSource).get(pos);
            } else {
                prevCity = a.tours.get(indexTourSource).get(pos - 1);
                currentCity = a.tours.get(indexTourSource).get(pos);
            }
            distance = VRPTW.instance.distance[prevCity + 1][currentCity + 1];
            arrivalTime = currentTime + reqList.get(prevCity + 1).getServiceTime() + distance;
            beginService = Math.max(arrivalTime, reqList.get(currentCity + 1).getStartWindow());
            if (beginService > reqList.get(currentCity + 1).getEndWindow()) {
                return false;
            }
            currentTime = beginService;
        }

//        3. 检查目标路径的时间窗约束
        //check feasibility for destination tour regarding time windows constraints
        for (int pos = j; pos < a.tours.get(indexTourDestination).size(); pos++) {
            if (pos == j) {
                prevCity = a.tours.get(indexTourDestination).get(pos - 1);
                currentCity = a.tours.get(indexTourSource).get(i);
                currentTime = a.beginService[prevCity + 1];
            } else if (pos == (j + 1)) {
                prevCity = a.tours.get(indexTourSource).get(i);
                currentCity = a.tours.get(indexTourDestination).get(pos);
            } else {
                prevCity = a.tours.get(indexTourDestination).get(pos - 1);
                currentCity = a.tours.get(indexTourDestination).get(pos);
            }
            distance = VRPTW.instance.distance[prevCity + 1][currentCity + 1];
            arrivalTime = currentTime + reqList.get(prevCity + 1).getServiceTime() + distance;
            beginService = Math.max(arrivalTime, reqList.get(currentCity + 1).getStartWindow());
            if (beginService > reqList.get(currentCity + 1).getEndWindow()) {
                return false;
            }
            currentTime = beginService;
        }

        return isFeasible;

    }

    //    更新执行exchange操作后的，两条路径中每个城市节点的开始服务时间，和两条路径的当前时间。
//    只需要更新发生变动的位置后面的城市序列
    static void updateBeginServiceExchangeMultiple(Ant a, VRPTW vrp, int indexTourSource, int indexTourDestination, int i, int j) {
        int currentCity, prevCity;
        double currentTime = 0.0;
        double distance, arrivalTime, beginService = 0.0;
        ArrayList<Request> reqList = vrp.getRequests();

//        1. 更新源路径
        for (int pos = i; pos < a.tours.get(indexTourSource).size() - 1; pos++) {
            prevCity = a.tours.get(indexTourSource).get(pos - 1);
            currentCity = a.tours.get(indexTourSource).get(pos);
            if (pos == i) {
                currentTime = a.beginService[prevCity + 1];
            }
            distance = VRPTW.instance.distance[prevCity + 1][currentCity + 1];
            arrivalTime = currentTime + reqList.get(prevCity + 1).getServiceTime() + distance;
            beginService = Math.max(arrivalTime, reqList.get(currentCity + 1).getStartWindow());
            currentTime = beginService;
            a.beginService[currentCity + 1] = beginService;
            if (beginService > reqList.get(currentCity + 1).getEndWindow()) {
                System.out.println("Exchange Multiple indexTourSource: Unfeasible solution..");
            }
        }
        a.currentTime.set(indexTourSource, beginService);

//        2. 更新目标路径
        for (int pos = j; pos < a.tours.get(indexTourDestination).size() - 1; pos++) {
            prevCity = a.tours.get(indexTourDestination).get(pos - 1);
            currentCity = a.tours.get(indexTourDestination).get(pos);
            if (pos == j) {
                currentTime = a.beginService[prevCity + 1];
            }
            distance = VRPTW.instance.distance[prevCity + 1][currentCity + 1];
            arrivalTime = currentTime + reqList.get(prevCity + 1).getServiceTime() + distance;
            beginService = Math.max(arrivalTime, reqList.get(currentCity + 1).getStartWindow());
            currentTime = beginService;
            a.beginService[currentCity + 1] = beginService;
            if (beginService > reqList.get(currentCity + 1).getEndWindow()) {
                System.out.println("Exchange Multiple indexTourDestination: Unfeasible solution..");
            }
        }
        a.currentTime.set(indexTourDestination, beginService);

    }

    //    尝试每种可能的exchange操作，找到最佳的操作，执行，并返回执行exchange后的蚂蚁a（相当于一次迭代）
    static Ant exchangeMultipleRoute(Ant a, VRPTW instance) {
        boolean feasible = false;
        int city1, city2, sourcePrevCity, sourceNextCity = -2, destinationPrevCity, destinationNextCity;
        int startIndexSource, startIndexDestination;
        double newQuantity1, newQuantity2, newDistance1, newDistance2, newTotalDistance;
        ArrayList<Request> reqList = instance.getRequests();
        int lastPos;

        Ant bestImprovedAnt = new Ant();
        bestImprovedAnt.tours = new ArrayList();
        bestImprovedAnt.tour_lengths = new ArrayList<Double>();
        bestImprovedAnt.beginService = new double[VRPTW.n + 1];
        bestImprovedAnt.currentTime = new ArrayList<Double>();
        bestImprovedAnt.currentQuantity = new ArrayList<Double>();
        bestImprovedAnt.usedVehicles = 1;
        for (int j = 0; j < bestImprovedAnt.usedVehicles; j++) {
            bestImprovedAnt.tours.add(j, new ArrayList<Integer>());
            bestImprovedAnt.tour_lengths.add(j, 0.0);
        }
        bestImprovedAnt.visited = new boolean[VRPTW.n];
        //the another node is the depot, which is by default visited by each salesman and added in its tour
        bestImprovedAnt.toVisit = instance.getIdAvailableRequests().size();
        bestImprovedAnt.costObjectives = new double[2];
        for (int indexObj = 0; indexObj < 2; indexObj++) {
            bestImprovedAnt.costObjectives[indexObj] = 0;
        }
        bestImprovedAnt.earliestTime = new ArrayList(bestImprovedAnt.usedVehicles);
        bestImprovedAnt.latestTime = new ArrayList(bestImprovedAnt.usedVehicles);

        Ant temp = new Ant();
        temp.tours = new ArrayList();
        temp.tour_lengths = new ArrayList<Double>();
        temp.beginService = new double[VRPTW.n + 1];
        temp.currentTime = new ArrayList<Double>();
        temp.currentQuantity = new ArrayList<Double>();
        temp.usedVehicles = 1;
        for (int j = 0; j < temp.usedVehicles; j++) {
            temp.tours.add(j, new ArrayList<Integer>());
            temp.tour_lengths.add(j, 0.0);
        }
        temp.visited = new boolean[VRPTW.n];
        //the another node is the depot, which is by default visited by each salesman and added in its tour
        temp.toVisit = instance.getIdAvailableRequests().size();
        temp.costObjectives = new double[2];
        for (int indexObj = 0; indexObj < 2; indexObj++) {
            temp.costObjectives[indexObj] = 0;
        }
        temp.earliestTime = new ArrayList(temp.usedVehicles);
        temp.latestTime = new ArrayList(temp.usedVehicles);

        Ants.copy_from_to(a, bestImprovedAnt, instance);
        Ants.copy_from_to(a, temp, instance);

        ArrayList<Integer> lastCommitedIndexes = new ArrayList<Integer>();
        for (int index = 0; index < Ants.best_so_far_ant.usedVehicles; index++) {
            lastPos = Controller.getLastCommitedPos(index);
            lastCommitedIndexes.add(lastPos);
        }

        for (int indexTourSource = 0; indexTourSource < (a.usedVehicles - 1); indexTourSource++) {
            for (int indexTourDestination = indexTourSource + 1; indexTourDestination < a.usedVehicles; indexTourDestination++) {
                if (indexTourSource != indexTourDestination) { // 只能交换不同路径中的的两个城市
                    //index of the element to be moved from the source tour
                    if (indexTourSource > lastCommitedIndexes.size() - 1) {
                        startIndexSource = 1;
                    } else {
                        startIndexSource = lastCommitedIndexes.get(indexTourSource) + 1;
                    }

                    //index of the element to be moved from the destination tour
                    if (indexTourDestination > lastCommitedIndexes.size() - 1) {
                        startIndexDestination = 1;
                    } else {
                        startIndexDestination = lastCommitedIndexes.get(indexTourDestination) + 1;
                    }
//                    路径末端城市应该是仓库，（或者路径末端城市也是通过特殊插入方式设置的）
                    for (int i = startIndexSource; i < a.tours.get(indexTourSource).size() - 1; i++) {
                        for (int j = startIndexDestination; j < a.tours.get(indexTourDestination).size() - 1; j++) {
                            if (indexTourSource <= indexTourDestination) {
                                //check if results a feasible solution (i.e. no time window constraint is violated)
                                feasible = checkFeasibleTourExchangeMultiple(temp, instance, indexTourSource, indexTourDestination, i, j);
                                if (feasible) {
                                    //obtain the neighbour solution corresponding to the relocation operator

//                                    1. 改变tours路径
                                    city1 = temp.tours.get(indexTourSource).get(i);
                                    city2 = temp.tours.get(indexTourDestination).get(j);
                                    temp.tours.get(indexTourSource).set(i, city2);
                                    temp.tours.get(indexTourDestination).set(j, city1);

//                                    2. 更新路径载量
                                    newQuantity1 = temp.currentQuantity.get(indexTourSource) - reqList.get(city1 + 1).getDemand() + reqList.get(city2 + 1).getDemand();
                                    temp.currentQuantity.set(indexTourSource, newQuantity1);
                                    newQuantity2 = temp.currentQuantity.get(indexTourDestination) - reqList.get(city2 + 1).getDemand() + reqList.get(city1 + 1).getDemand();
                                    temp.currentQuantity.set(indexTourDestination, newQuantity2);

//                                    3. update the begin service times of the nodes from the source and destination tours of the obtained neighbour solution
//                                      also update the current time of the source and destination tours
                                    updateBeginServiceExchangeMultiple(temp, instance, indexTourSource, indexTourDestination, i, j);

//                                    4. update total traveled distance and lengths of source and destination tours
                                    sourcePrevCity = temp.tours.get(indexTourSource).get(i - 1);
                                    sourceNextCity = temp.tours.get(indexTourSource).get(i + 1);
                                    newDistance1 = temp.tour_lengths.get(indexTourSource) - VRPTW.instance.distance[sourcePrevCity + 1][city1 + 1] - VRPTW.instance.distance[city1 + 1][sourceNextCity + 1] + VRPTW.instance.distance[sourcePrevCity + 1][city2 + 1] + VRPTW.instance.distance[city2 + 1][sourceNextCity + 1];

                                    destinationPrevCity = temp.tours.get(indexTourDestination).get(j - 1);
                                    destinationNextCity = temp.tours.get(indexTourDestination).get(j + 1);
                                    newDistance2 = temp.tour_lengths.get(indexTourDestination) - VRPTW.instance.distance[destinationPrevCity + 1][city2 + 1] - VRPTW.instance.distance[city2 + 1][destinationNextCity + 1] + VRPTW.instance.distance[destinationPrevCity + 1][city1 + 1] + VRPTW.instance.distance[city1 + 1][destinationNextCity + 1];

                                    newTotalDistance = temp.total_tour_length - temp.tour_lengths.get(indexTourSource) - temp.tour_lengths.get(indexTourDestination) + newDistance1 + newDistance2;
                                    temp.total_tour_length = newTotalDistance;
                                    temp.tour_lengths.set(indexTourSource, newDistance1);
                                    temp.tour_lengths.set(indexTourDestination, newDistance2);

//                                    5. if some improvement is obtained in the total traveled distance
                                    if (temp.total_tour_length < bestImprovedAnt.total_tour_length) {
                                        Ants.copy_from_to(temp, bestImprovedAnt, instance);
                                    }

//                                    6. restore previous solution constructed by ant
                                    Ants.copy_from_to(a, temp, instance);
                                }
                            }
                        }
                    }
                }
            }
        }
        return bestImprovedAnt;
    }

    //   exchange算子。一次迭代：遍历所有可能对调的位置，进行尝试对调，找到一个最优的exchange，并保存至原来的蚂蚁a。
//	将上述操作定义为一次迭代，进行多次迭代，直至某次迭代不能找到更优解为止。
//	返回最终迭代得到的蚂蚁
    static Ant exchangeMultipleRouteIterated(Ant a, VRPTW instance) {
        boolean feasible = false;
        int city1, city2, sourcePrevCity, sourceNextCity = -2, destinationPrevCity, destinationNextCity;
        int startIndexSource, startIndexDestination;
        double newQuantity1, newQuantity2, newDistance1, newDistance2, newTotalDistance;
        ArrayList<Request> reqList = instance.getRequests();
        boolean foundImprovement = true, isValid;
        int lastPos;
        double tempNo = Math.pow(10, 10);
        double round1, round2;

        Ant improvedAnt = new Ant();
        improvedAnt.tours = new ArrayList();
        improvedAnt.tour_lengths = new ArrayList<Double>();
        improvedAnt.beginService = new double[VRPTW.n + 1];
        improvedAnt.currentTime = new ArrayList<Double>();
        improvedAnt.currentQuantity = new ArrayList<Double>();
        improvedAnt.usedVehicles = 1;
        for (int j = 0; j < improvedAnt.usedVehicles; j++) {
            improvedAnt.tours.add(j, new ArrayList<Integer>());
            improvedAnt.tour_lengths.add(j, 0.0);
        }
        improvedAnt.visited = new boolean[VRPTW.n];
        //the another node is the depot, which is by default visited by each salesman and added in its tour
        improvedAnt.toVisit = instance.getIdAvailableRequests().size();
        improvedAnt.costObjectives = new double[2];
        for (int indexObj = 0; indexObj < 2; indexObj++) {
            improvedAnt.costObjectives[indexObj] = 0;
        }
        improvedAnt.earliestTime = new ArrayList(improvedAnt.usedVehicles);
        improvedAnt.latestTime = new ArrayList(improvedAnt.usedVehicles);

        Ant temp = new Ant();
        temp.tours = new ArrayList();
        temp.tour_lengths = new ArrayList<Double>();
        temp.beginService = new double[VRPTW.n + 1];
        temp.currentTime = new ArrayList<Double>();
        temp.currentQuantity = new ArrayList<Double>();
        temp.usedVehicles = 1;
        for (int j = 0; j < temp.usedVehicles; j++) {
            temp.tours.add(j, new ArrayList<Integer>());
            temp.tour_lengths.add(j, 0.0);
        }
        temp.visited = new boolean[VRPTW.n];
        //the another node is the depot, which is by default visited by each salesman and added in its tour
        temp.toVisit = instance.getIdAvailableRequests().size();
        temp.costObjectives = new double[2];
        for (int indexObj = 0; indexObj < 2; indexObj++) {
            temp.costObjectives[indexObj] = 0;
        }
        temp.earliestTime = new ArrayList(temp.usedVehicles);
        temp.latestTime = new ArrayList(temp.usedVehicles);

        Ants.copy_from_to(a, improvedAnt, instance);
        Ants.copy_from_to(a, temp, instance);

        ArrayList<Integer> lastCommitedIndexes = new ArrayList<Integer>();
        for (int index = 0; index < Ants.best_so_far_ant.usedVehicles; index++) {
            lastPos = Controller.getLastCommitedPos(index);
            lastCommitedIndexes.add(lastPos);
        }

        int count = 0;
        while (foundImprovement) {
            foundImprovement = false;

            count++;
            if (count > 100) {
                System.out.println("Inside exchangeMultipleRouteIterated; count=" + count);
            }

            Ants.copy_from_to(improvedAnt, a, instance);
            Ants.copy_from_to(improvedAnt, temp, instance);

            for (int indexTourSource = 0; indexTourSource < (temp.usedVehicles - 1); indexTourSource++) {
                for (int indexTourDestination = indexTourSource + 1; indexTourDestination < temp.usedVehicles; indexTourDestination++) {
                    if (indexTourSource != indexTourDestination) {
                        //index of the element to be moved from the source tour
                        if (indexTourSource > lastCommitedIndexes.size() - 1) {
                            startIndexSource = 1;
                        } else {
                            startIndexSource = lastCommitedIndexes.get(indexTourSource) + 1;
                        }

                        //index of the element to be moved from the destination tour
                        if (indexTourDestination > lastCommitedIndexes.size() - 1) {
                            startIndexDestination = 1;
                        } else {
                            startIndexDestination = lastCommitedIndexes.get(indexTourDestination) + 1;
                        }
                        for (int i = startIndexSource; i < temp.tours.get(indexTourSource).size() - 1; i++) {
                            for (int j = startIndexDestination; j < temp.tours.get(indexTourDestination).size() - 1; j++) {
                                if (indexTourSource <= indexTourDestination) {
                                    //check if results a feasible solution (i.e. no time window constraint is violated)
                                    feasible = checkFeasibleTourExchangeMultiple(temp, instance, indexTourSource, indexTourDestination, i, j);
                                    if (feasible) {
                                        //obtain the neighbour solution corresponding to the relocation operator
                                        city1 = temp.tours.get(indexTourSource).get(i);
                                        city2 = temp.tours.get(indexTourDestination).get(j);
                                        temp.tours.get(indexTourSource).set(i, city2);
                                        temp.tours.get(indexTourDestination).set(j, city1);
									    
									    /*isValid = Utilities.checkFeasibility(temp, instance, false);
							    	    if (!isValid) {
							    	    	System.out.println("Inside exchangeMultipleRouteIterated: The resulted solution is not valid (feasible)..");
							    	    }*/

                                        newQuantity1 = temp.currentQuantity.get(indexTourSource) - reqList.get(city1 + 1).getDemand() + reqList.get(city2 + 1).getDemand();
                                        temp.currentQuantity.set(indexTourSource, newQuantity1);
                                        newQuantity2 = temp.currentQuantity.get(indexTourDestination) - reqList.get(city2 + 1).getDemand() + reqList.get(city1 + 1).getDemand();
                                        temp.currentQuantity.set(indexTourDestination, newQuantity2);

                                        //update the begin service times of the nodes from the source and destination tours of the obtained neighbour solution
                                        //also update the current time of the source and destination tours
                                        updateBeginServiceExchangeMultiple(temp, instance, indexTourSource, indexTourDestination, i, j);

                                        //update total traveled distance and lengths of source and destination tours
                                        sourcePrevCity = temp.tours.get(indexTourSource).get(i - 1);
                                        sourceNextCity = temp.tours.get(indexTourSource).get(i + 1);
                                        newDistance1 = temp.tour_lengths.get(indexTourSource) - VRPTW.instance.distance[sourcePrevCity + 1][city1 + 1] - VRPTW.instance.distance[city1 + 1][sourceNextCity + 1] + VRPTW.instance.distance[sourcePrevCity + 1][city2 + 1] + VRPTW.instance.distance[city2 + 1][sourceNextCity + 1];

                                        destinationPrevCity = temp.tours.get(indexTourDestination).get(j - 1);
                                        destinationNextCity = temp.tours.get(indexTourDestination).get(j + 1);
                                        newDistance2 = temp.tour_lengths.get(indexTourDestination) - VRPTW.instance.distance[destinationPrevCity + 1][city2 + 1] - VRPTW.instance.distance[city2 + 1][destinationNextCity + 1] + VRPTW.instance.distance[destinationPrevCity + 1][city1 + 1] + VRPTW.instance.distance[city1 + 1][destinationNextCity + 1];

                                        newTotalDistance = temp.total_tour_length - temp.tour_lengths.get(indexTourSource) - temp.tour_lengths.get(indexTourDestination) + newDistance1 + newDistance2;
                                        temp.total_tour_length = newTotalDistance;
                                        temp.tour_lengths.set(indexTourSource, newDistance1);
                                        temp.tour_lengths.set(indexTourDestination, newDistance2);

                                        //performing the rounding of the two numbers up to 10 decimals so that in the
                                        //comparison of the 2 double values to consider only the first 10 most significant decimals
                                        round1 = Math.round(temp.total_tour_length * tempNo) / tempNo;
                                        round2 = Math.round(improvedAnt.total_tour_length * tempNo) / tempNo;
                                        //if some improvement is obtained in the total traveled distance
                                        if (round1 < round2) {
                                            Ants.copy_from_to(temp, improvedAnt, instance);
                                            foundImprovement = true;
                                        }

                                        //restore previous solution constructed by ant
                                        Ants.copy_from_to(a, temp, instance);
                                    }
                                }

                            }
                        }
                    }

                }
            }
        }

        return improvedAnt;
    }

    /**
     * 更新统计信息
     * manage some statistical information about the trial, especially if a new best solution (best-so-far) is found
     * and adjust some parameters if a new best solution is found
     */
    static void update_statistics(VRPTW instance) {
        int iteration_best_ant;
        double scalingValue, scalledValue = 0.0, sum;
        Object obj = new Object();
        double round1, round2;
        double tempNo = Math.pow(10, 10);

        // 1.获取当前最优蚂蚁a（当前最优解的）
        iteration_best_ant = Ants.find_best(); /* iteration_best_ant is a global variable */
        //Ants.ants[iteration_best_ant] = local_search(Ants.ants[iteration_best_ant]);
        Ant a = Ants.ants[iteration_best_ant];
        //System.out.println("Entering update_statistics");

        // 2.继续对蚂蚁a进行邻域搜索，尝试找到优于a的蚂蚁，并替换a
        // boolean isValid;
        if (ls_flag) { // 如果允许进行迭代操作
			/*isValid = Utilities.checkFeasibility(a, instance, false);
    	    if (!isValid) {
    	    	System.out.println("Before relocateMultipleRouteIterated: The resulted solution is not valid (feasible)..");
    	    }
            apply multiple route relocation and exchange iterated local search operators for the iteration best ant */
            // 从当前最优解a出发，再进行邻域搜索，寻找更优的解
            a = relocateMultipleRouteIterated(a, instance); // 重定位算子
        	/*isValid = Utilities.checkFeasibility(a, instance, false);
    	    if (!isValid) {
    	    	System.out.println("After relocateMultipleRouteIterated: The resulted solution is not valid (feasible)..");
    	    }
            System.out.println("Exited relocateMultipleRouteIterated");*/
            a = exchangeMultipleRouteIterated(a, instance); // 交换算子
            /* System.out.println("Exited exchangeMultipleRouteIterated");
        	isValid = Utilities.checkFeasibility(a, instance, false);
    	    if (!isValid) {
    	    	System.out.println("After exchangeMultipleRouteIterated: The resulted solution is not valid (feasible)..");
    	    } */
        }

        // 3.使用再次优化后得到的a，更新当前最优解（此处使用了线程互斥锁）
        synchronized (obj) {
            round1 = Math.round(a.total_tour_length * tempNo) / tempNo;
            round2 = Math.round(Ants.best_so_far_ant.total_tour_length * tempNo) / tempNo;
            if ((a.usedVehicles < Ants.best_so_far_ant.usedVehicles) // 使用车辆数量的优势
                    || ((a.usedVehicles == Ants.best_so_far_ant.usedVehicles) && (round1 < round2)) // 车辆数量相等时，以一定概率接受a
                    || ((round1 < round2) && (Ants.best_so_far_ant.total_tour_length == Double.MAX_VALUE)))
            {
                // best solution found after time_used（记录一下运行到现在花费的时间）
                InOut.time_used = Timer.elapsed_time();
			    /*if (a.usedVehicles < Ants.best_so_far_ant.usedVehicles) {
			    	for (int i = a.usedVehicles; i < Ants.best_so_far_ant.usedVehicles; i++) {
			    		Ants.lastCommitted.remove(a.usedVehicles);
			    	}
			    }*/
                Ants.copy_from_to(a, Ants.best_so_far_ant, instance);
                scalingValue = Controller.getScalingValue();
                /* if (scalingValue != 0) {
                    scalledValue = Ants.best_so_far_ant.total_tour_length / scalingValue;
                } */
			    /*System.out.println("Updated Best so far ant >> No. of used vehicles=" + Ants.best_so_far_ant.usedVehicles + " total tours length=" + Ants.best_so_far_ant.total_tour_length + " (scalled value = " + scalledValue + ")");
			    for (int i = 0; i < Ants.best_so_far_ant.usedVehicles; i++) {
					int tourLength = Ants.best_so_far_ant.tours.get(i).size();
					for (int j = 0; j < tourLength; j++) {
						int city = Ants.best_so_far_ant.tours.get(i).get(j);
						//only for Unix shell prompts: print committed nodes with red color at console
						if (city >= 0) {
							if (Ants.committedNodes[city]) {
								System.out.print(Utilities.ANSI_RED);
							}
						}
						
						//so as to correspond to the city indexes from the VRPTW input file
						System.out.print((city + 1) + " ");	
						//reset color	
						if (city >= 0) {
							if (Ants.committedNodes[city]) {
								System.out.print(Utilities.ANSI_RESET);
							}
						}
					}
					System.out.println();
					//System.out.print(Utilities.ANSI_RESET);
				}
			    isValid = Utilities.checkFeasibility(Ants.best_so_far_ant, instance, true);
	    	    if (!isValid) {
	    	    	System.out.println("Inside update_statistics: The solution is not valid (feasible)..");
	    	    }
	    	    else if (isValid) {
	    	    	System.out.println("Inside update_statistics: The solution is valid (feasible)..");
	    	    }*/
            }
        }
    }

    /**
     * 记录下当前迭代得到的最优蚂蚁，并用其更新当前最优蚂蚁和当前一蚁群中的最优蚂蚁
     * manage some statistical information about the trial, especially if a new best solution
     * (best-so-far) is found and adjust some parameters if a new best solution is found
     *
     * @param saveIterCosts：是否要记录每次蚁群迭代的数据
     * @param instance：问题实例
     */
    static void update_statistics(boolean saveIterCosts, VRPTW instance) {

//		1. 返回当前迭代的代数的最优蚂蚁a
        /* iteration_best_ant is a global variable */
        int iteration_best_ant;
        iteration_best_ant = Ants.find_best();
        Ant a = Ants.ants[iteration_best_ant];

        //a = relocationIterated(a);
		
		/*if (ls_flag) {
			//apply exchange local search operator for the iteration best ant
			a = exchangeIterated(a, instance); 
			
			//apply 2-opt heuristic on each of the m routes; 2-opt tries to improve single route
			//by replacing its two non-adjacent edges by two other edges
			for (int l = 0; l < a.usedVehicles; l++) {
				LocalSearch.two_opt_first(a.tours.get(l));
			}
			
			//compute new distances and update longest tour
			double sum = 0.0;
			double longestTourLength = Double.MIN_VALUE;
			int idLongestTour = 0;
			for (int l = 0; l < a.usedVehicles; l++) {
				a.tour_lengths.set(l, VRPTW.compute_tour_length(a.tours.get(l)));
				sum += a.tour_lengths.get(l);
				if (longestTourLength < a.tour_lengths.get(l)) {
					longestTourLength = a.tour_lengths.get(l);
					idLongestTour = l;
				}
			}
			a.total_tour_length = sum;
			a.longest_tour_length = longestTourLength;
			a.indexLongestTour = idLongestTour;
		}*/

//		2. 如果蚂蚁a优于全局最优的蚂蚁best_so_far_ant，则将蚂蚁a赋值给best_so_far_ant和restart_best_ant
        if ((a.usedVehicles < Ants.best_so_far_ant.usedVehicles) || (a.usedVehicles == Ants.best_so_far_ant.usedVehicles) && (a.total_tour_length < Ants.best_so_far_ant.total_tour_length)
                || ((a.total_tour_length < Ants.best_so_far_ant.total_tour_length) && (Ants.best_so_far_ant.total_tour_length == Double.MAX_VALUE))) {

            InOut.time_used = Timer.elapsed_time();  //best solution found after time_used
            Ants.copy_from_to(a, Ants.best_so_far_ant, instance);
            Ants.copy_from_to(a, Ants.restart_best_ant, instance);

            InOut.found_best = InOut.iteration; // 记录下找到最优蚂蚁的迭代次数
            InOut.restart_found_best = InOut.iteration; // 记录下再次找到最优蚂蚁的迭代次数
            //InOut.branching_factor = InOut.node_branching(InOut.lambda);
            //System.out.println("Iter: " + InOut.iteration + " Best ant -> longest tour=" + Ants.best_so_far_ant.longest_tour_length + ", b_fac " + InOut.branching_factor);
            //System.out.println("Iter: " + InOut.iteration + " Best ant -> longest tour=" + Ants.best_so_far_ant.longest_tour_length);
            //System.out.println("Iter: " + InOut.iteration + " Best ant >> No. of used vehicles=" + Ants.best_so_far_ant.usedVehicles + " total tours length=" + Ants.best_so_far_ant.total_tour_length);
        }

//		3. 如果蚂蚁a优于当前蚁群的最优蚂蚁restart_best_ant，则将蚂蚁a赋值给restart_best_ant
        if ((a.usedVehicles < Ants.restart_best_ant.usedVehicles) || (a.usedVehicles == Ants.restart_best_ant.usedVehicles) && (a.total_tour_length < Ants.restart_best_ant.total_tour_length)
                || ((a.total_tour_length < Ants.restart_best_ant.total_tour_length) && (Ants.restart_best_ant.total_tour_length == Double.MAX_VALUE))) {
            Ants.copy_from_to(a, Ants.restart_best_ant, instance);

            InOut.restart_found_best = InOut.iteration;
            //System.out.println("Iter: " + InOut.iteration + " Restart best ant >> No. of used vehicles=" + Ants.restart_best_ant.usedVehicles + " total tours length=" + Ants.restart_best_ant.total_tour_length);
        }
		
		/*if (!saveIterCosts) {
			//compute non-dominated set of solutions (iteration non-dominated front)
			ParetoFront.iterationPareto.clear();
			Ant copyAnt;
			for (int i = 0; i < Ants.n_ants; i++) {
				copyAnt = Ants.copyAnt(Ants.ants[i]);
				ParetoFront.paretoUpdateWithSolution(ParetoFront.iterationPareto, copyAnt);
			}
			
			//update BestSoFarPareto external set
			ParetoFront.paretoUpdate(ParetoFront.bestSoFarPareto, ParetoFront.iterationPareto);
		}*/
    }

    // 这个方法没用到
    //occasionally compute some statistics
    //at every 5 iterations save the value of the longest cost of the solution/tour given by the best so far ant
    static void search_control_and_statistics() {
        double longestCost;
        double initTrail;
    	
    	/*if (saveDetailedOutput) {
    		if ((InOut.iteration % 5) == 0) {
			    //System.out.println("TSP(" + tspIndex + "): best tour length so far " + Ants.best_so_far_ant[tspIndex].tour_length + ", iteration: " + InOut.iteration);
	    		longestCost = Ants.best_so_far_ant.total_tour_length;
	    		
	    		iterLongestCost.add(longestCost);
	    		if (trial == 0) {
	    			iterNumber.add(InOut.iteration);
	    		}
    		}
    	}*/
    	
    	/*if ((InOut.iteration % 5) == 0) {
    	    InOut.branching_factor = InOut.node_branching(InOut.lambda);
    	    //System.out.println("Iter: " + InOut.iteration + ", b_fac " + InOut.branching_factor);

    	    //if (InOut.iteration - InOut.restart_found_best >= 200) {
    	    if (((InOut.branching_factor <= InOut.branch_fac) && (InOut.iteration - InOut.restart_found_best > 100)) || ((InOut.iteration - InOut.restart_found_best >= 300))) {
    			// Ants.pheromone trail re-initialisation takes place
    			//System.out.println("Reinitialisation of pheromone trails...");
    			Ants.restart_best_ant.total_tour_length = Double.MAX_VALUE;
    			initTrail = 1. / ((double) (VRPTW.n + 1) * (Ants.best_so_far_ant.total_tour_length * Ants.best_so_far_ant.usedVehicles));
    			Ants.init_pheromone_trails(initTrail);
    	    }
    	}*/
    }

    /**
     * occasionally compute some statistics
     * at every 5 iterations save the value of the longest cost of the solution/tour given by the best so far ant
     *
     * @param iterLongestCost：记录当前最优解中的，总的路径长度
     * @param iterNumber：记录当前最优解中的，总的路径长度对应的迭代次数
     * @param saveDetailedOutput：是否要输结果
     * @param trial：测试次数
     */
    static void search_control_and_statistics(ArrayList<Double> iterLongestCost, ArrayList<Integer> iterNumber, boolean saveDetailedOutput, int trial) {
        double longestCost;
        double initTrail;

        if (saveDetailedOutput) {
            if ((InOut.iteration % 5) == 0) {
                //System.out.println("TSP(" + tspIndex + "): best tour length so far " + Ants.best_so_far_ant[tspIndex].tour_length + ", iteration: " + InOut.iteration);
                longestCost = Ants.best_so_far_ant.total_tour_length;

                iterLongestCost.add(longestCost);
                if (trial == 0) {
                    iterNumber.add(InOut.iteration);
                }
            }
        }
    	
    	/*if ((InOut.iteration % 5) == 0) {
    	    InOut.branching_factor = InOut.node_branching(InOut.lambda);
    	    //System.out.println("Iter: " + InOut.iteration + ", b_fac " + InOut.branching_factor);

    	    //if (InOut.iteration - InOut.restart_found_best >= 200) {
    	    if (((InOut.branching_factor <= InOut.branch_fac) && (InOut.iteration - InOut.restart_found_best > 100)) || ((InOut.iteration - InOut.restart_found_best >= 300))) {
    			// Ants.pheromone trail re-initialisation takes place
    			//System.out.println("Reinitialisation of pheromone trails...");
    			Ants.restart_best_ant.total_tour_length = Double.MAX_VALUE;
    			initTrail = 1. / ((double) (VRPTW.n + 1) * (Ants.best_so_far_ant.total_tour_length * Ants.best_so_far_ant.usedVehicles));
    			Ants.init_pheromone_trails(initTrail);
    	    }
    	}*/
    }

    //更新全局信息素（as）manage global Ants.pheromone deposit for Ant System
    static void as_update() {
        int k;
        for (k = 0; k < Ants.n_ants; k++)
            Ants.global_update_pheromone(Ants.ants[k]);
    }

    // 更新全局信息素（acs）
    // manage global Ants.pheromone deposit for Ant Colony System
    static void acs_global_update() {
        Ants.global_acs_pheromone_update(Ants.best_so_far_ant);
    	
    	/*if (InOut.iteration - InOut.restart_found_best > 100) {
    		//System.out.println("Using best so far ant for global pheromone update");
    		Ants.global_acs_pheromone_update(Ants.best_so_far_ant);
    	}
    	else {
    		//System.out.println("Using restart best ant for global pheromone update");
    		Ants.global_acs_pheromone_update(Ants.restart_best_ant);
    	}*/

    }

    // 更新全局信息素（ACO）
    // manage global Ants.pheromone trail update for the ACO algorithms
    static void pheromone_trail_update() {
        // Simulate the Ants.pheromone evaporation of all Ants.pheromones; this is not necessary for ACS
        if (Ants.as_flag) {
            Ants.evaporation();/* evaporate all Ants.pheromone trails 全局信息素衰减 */
        }

        /* Next, apply the Ants.pheromone deposit for the various ACO algorithms */
        if (Ants.as_flag)
            as_update();
        else if (Ants.acs_flag)
            acs_global_update();
        /*
         * Compute combined information Ants.pheromone times heuristic info after
         * the Ants.pheromone update for all ACO algorithms except ACS; in the ACS case
         * this is already done in the Ants.pheromone update procedures of ACS
         */
        if (Ants.as_flag) {
            //Ants.compute_total_information();
        }
    }

    // 使蚁群系统结束执行
    public void terminate() {
        isRunning = false;
    }

    public static void main(String[] args) {
        boolean saveIterCosts = false; // 是否要记录迭代中的成本

        for (int trial = 0; trial < 1; trial++) { // 对于优化系统，只执行一次测试就行
            long startTime = System.currentTimeMillis(); // 优化系统的开始时间

//			1. 从文件中读出问题：vrpInstance
            //read the data from the input file
            DataReader reader = new DataReader(Controller.vrpInstance);
            //read the data from the file
            VRPTW vrpInstance = reader.read();
            System.out.println("\nDVRPTW_ACS MinSum>> Solving dynamic VRPTW instance: " + VRPTW.instance.name);
            System.out.println("No. of customers' requests (except the depot): " + VRPTW.n);

//			2. 初始化优化程序（设置默认参数；执行命令语句；设置蚂蚁数量；计算距离矩阵）
            InOut.init_program(args, trial, vrpInstance, 0.0);

//			3. 计算每个城市的邻近城市的编号数组,按照距离排列
            int[][][] result = new int[2][][];
            result = VRPTW.compute_nn_lists(vrpInstance);
            VRPTW.instance.nn_list = result[0];
            VRPTW.instance.nn_list_all = result[1];

//			4. 初始化信息素矩阵
            Ants.pheromone = new double[VRPTW.n + 1][VRPTW.n + 1];
            init_try(vrpInstance);

            generateInitialWeights(); // 计算mij的三个权重

//			5. 初始化记录迭代成本的两个列表
            ArrayList<Double> iterLongestCost = null;
            ArrayList<Integer> iterNumber = null;
            if (saveIterCosts) {
                //for saving detailed cost values at each 5 iterations
                iterLongestCost = new ArrayList<Double>(); // 记录：当前最优解中最长路径的长度
                iterNumber = new ArrayList<Integer>(); // 记录：当前最优解中最长路径的结点
            }

//			6. 进行蚁群的迭代
            InOut.iteration = 0; // 开始迭代次数为0
            while (!termination_condition()) { // 在允许蚁群系统优化的最大时间范围内，进行蚁群迭代优化，超出时间则跳出优化

//				6.1 构造本次迭代得到的解
                construct_solutions(vrpInstance);

//				6.2 更新当前最优解和本次迭代得到的最优解
                update_statistics(saveIterCosts, vrpInstance);

//				6.3 更新信息素
                pheromone_trail_update();

//				6.4 每迭代五次，就记录一次当前最优解的总路径长度和对应的迭代次数
                search_control_and_statistics(iterLongestCost, iterNumber, saveIterCosts, trial);

//				6.5 进入下一次迭代
                InOut.iteration++;
            }

//          7. 打印本次测试的结果，并将测试结果传入Utilities类中，用于存储至文件的操作
            InOut.exit_try(trial);
		   /* if (!saveIterCosts) {
		    	Utilities.writeParetoSet(ParetoFront.bestSoFarPareto, trial);
			    //System.out.println("Reached " + InOut.iteration + " iterations");
			    //Utilities.writeExcel(MTsp.n, MTsp.m, totalLength);
		    	Utilities.writeParetoSolutions(ParetoFront.bestSoFarPareto);
			    ParetoFront.bestSoFarPareto.clear();
		    }*/
            // Utilities.writeResultsExcel(trial, saveIterCosts);

//          8. 打印测试消耗的时间和迭代的次数
            long endTime = System.currentTimeMillis();
            double difference1 = (endTime - startTime) / 1000.0;
            System.out.println("Run #" + (trial + 1) + " Elapsed seconds: " + difference1 + " Ellapsed iterations: " + InOut.iteration);
		  
		  /*double difference2 = (endCPUTime - startCPUTime)/1000000000.0;
		  System.out.println("\nRun #" + (trial + 1)  + " Elapsed seconds (CPU time): " + difference2); */
        }
    }
}